package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * db
 * 1770. 执行乘法运算的最大分数
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/11 17:10
 */
public class MaximumScore {


    public static void main(String[] args) {
        MaximumScore test = new MaximumScore();

        // 14
//        int[] nums = {1, 2, 3};
//        int[] multipliers = {3, 2, 1};

        // 102
        int[] nums = {-5, -3, -3, -2, 7, 1};
        int[] multipliers = {-10, -5, 3, 4, 6};

        int i = test.maximumScore(nums, multipliers);
        System.out.println(i);

    }


    public int maximumScore(int[] nums, int[] multipliers) {
        int n = nums.length;
        int m = multipliers.length;
        int[] arr = new int[n];
        for (int i = m - 1; i >= 0; i--) {
            int v = multipliers[i];
            for (int j = 0; j <= i; j++) {
                int a = i + 1 == m ? 0 : arr[j + 1];
                int b = i + 1 == m ? 0 : arr[j];
                arr[j] = Math.max(v * nums[j] + a, v * nums[j + n - 1 - i] + b);
            }
        }
        return arr[0];
    }

}
